package alogrithm;

import java.util.Arrays;

/**
 * @author lbw
 * @version 1.0
 * @date 2021/9/10 22:16
 */
public class HeapSortTest {
    public static void main(String[] args) {

        int[] a = new int[]{1, 7, 5, 6, 4, 2, 3};
        heapSort(a);
        System.out.println(Arrays.toString(a));
    }

    private static void heapSort(int[] a) {

        // 从最后一个子树的父节点开始处理
        for (int i = a.length / 2; i >= 0; i--) {
            adjustHeap(a, i, a.length);
        }

        // 处理完后得到一个堆, 然后将堆顶元素, 交换至未完成排序数组的末尾, 实现排序
        for (int j = a.length - 1; j >= 0; --j) {
            int temp = a[0];
            a[0] = a[j];
            a[j] = temp;
            adjustHeap(a, 0, j);
        }
    }

    private static void adjustHeap(int[] a, int i, int j) {
        // 先保存当前父节点的的值
        int temp = a[i];
        // 递归处理该父节点下的所有子树
        for (int k = i * 2 + 1; k < j; k = k * 2 + 1) {
            // 右孩子>左孩子, 处理右孩子
            if (k + 1 < j && a[k] < a[k + 1]) {
                k++;
            }
            // 如果子节点大于父节点, 将子节点的值赋给父节点, 然后记录下交换后的子节点的位置
            if (temp < a[k]) {
                a[i] = a[k];
                i = k;
            } else {
                break;
            }
        }
        // 将交换后的父节点的值放在合适的位置
        a[i] = temp;
    }
}
